package link;

/**
 * 给你一个链表数组，每个链表都已经按升序排列。
 *
 * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
 */
public class leetCode23_mergeKLists {

    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists,0,lists.length - 1);
    }
    public ListNode merge(ListNode[] lists, int l ,int r){
        if(l == r) return lists[l];
        if(l > r) return null;
        int mid = l + (r - l)/2;

        return mergeTwoListNode(merge(lists,l,mid),merge(lists,mid + 1,r));
    }



    public ListNode mergeTwoListNode(ListNode a,ListNode b){
        if(a == null) return b;
        if(b == null) return a;
        ListNode result = new ListNode(-1);
        ListNode tmp = result;
        while (a != null && b != null){
            int i = a.val;
            int j = b.val;
            if(i < j){
                tmp.next = a;
                a = a.next;
            }else{
                tmp.next = b;
                b = b.next;
            }
            tmp = tmp.next;
        }
        tmp.next = a == null?b:a;
        return result.next;
    }


    public static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
        }
    }
}
